home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / bptree.zip / BPTREE.C < prev    next >
Text File  |  1992-09-04  |  10KB  |  272 lines
  1. //-----------------------------------------------------------------
  2. // BPTREE.C
  3. //
  4. // BPlus Tree management functions
  5. //
  6. //-----------------------------------------------------------------
  7.  
  8. #ifdef __WINMEM__
  9.    #include <windows.h>
  10. #endif
  11. #include "bptree.h"
  12.  
  13. //-----------------------------------------------------------------
  14. // BPlus tree structure allocation and deallocation functions
  15. //-----------------------------------------------------------------
  16.  
  17. TREENODEPTR LIBFUNC MakeINode( ) {
  18.    TREENODEPTR  tNode;
  19.    tNode = (TREENODEPTR)Malloc( sizeof( TREENODE ) );
  20.    tNode->nodeType = BPT_INODE;
  21.    return( tNode );
  22. }
  23.  
  24. void LIBFUNC FreeINode( TREENODEPTR tNode ) {
  25.    Free( tNode ); 
  26.    return;  
  27. }
  28.  
  29. TREENODEPTR LIBFUNC MakeLNode( ) {
  30.    TREENODEPTR  tNode;
  31.    tNode = (TREENODEPTR)Malloc( sizeof( TREENODE ) );
  32.    tNode->nodeType = BPT_LNODE;
  33.    return( tNode );
  34. }
  35.  
  36. void LIBFUNC FreeLNode( TREENODEPTR tNode ) {
  37.    Free( tNode );
  38.    return;
  39. }
  40.  
  41. KEYPTR LIBFUNC MakeMemBuf( int size ) {
  42.    return( (KEYPTR)Malloc( size ) );
  43. }
  44.  
  45. void LIBFUNC FreeMemBuf( KEYPTR szBuf ) {
  46.    Free( szBuf );
  47. }
  48.  
  49. //-----------------------------------------------------------------
  50. // Recursive node insertion routine
  51. //-----------------------------------------------------------------
  52.  
  53. TREENODEPTR LIBFUNC InsertTreeNode( PTR2TREENODEPTR tree,  KEYPTR key, DATAPTR data ) {
  54.    TREENODEPTR newINode, newLNode, tNode;
  55.    if ( (*tree)->nodeType == BPT_LNODE ) {
  56.       newINode = MakeINode( );
  57.       newLNode = MakeLNode( );
  58.       newLNode->lnode.keyValue = MakeMemBuf( StrLen( key ) + 1 );
  59.       StrCpy( newLNode->lnode.keyValue, key );
  60.       newLNode->lnode.data = data;
  61.       if ( StrCmp( key, (*tree)->lnode.keyValue ) >= 0 ) {
  62.          newINode->inode.left = *tree;
  63.          newINode->inode.right = newLNode;
  64.          newINode->inode.keyValue = MakeMemBuf( StrLen( key ) + 1 );
  65.          StrCpy( newINode->inode.keyValue, key );
  66.          (*tree)->lnode.next->lnode.prev = newLNode;
  67.          newLNode->lnode.next = (*tree)->lnode.next;
  68.          (*tree)->lnode.next = newLNode;
  69.          newLNode->lnode.prev = *tree;
  70.       } else {
  71.          newINode->inode.left = newLNode;
  72.          newINode->inode.right = *tree;
  73.          newINode->inode.keyValue = MakeMemBuf( StrLen( (*tree)->lnode.keyValue ) + 1 );
  74.          StrCpy( newINode->inode.keyValue, (*tree)->lnode.keyValue );
  75.          (*tree)->lnode.prev->lnode.next = newLNode;
  76.          newLNode->lnode.prev = (*tree)->lnode.prev;
  77.          (*tree)->lnode.prev = newLNode;
  78.          newLNode->lnode.next = *tree;
  79.       }
  80.       *tree = newINode;
  81.       return( newLNode );
  82.    } else {
  83.       if ( StrCmp( key, (*tree)->inode.keyValue ) >= 0 ) {
  84.          tNode = InsertTreeNode( (PTR2TREENODEPTR)(&((*tree)->inode.right)), key, data );
  85.       } else {
  86.          tNode = InsertTreeNode( (PTR2TREENODEPTR)(&((*tree)->inode.left)), key, data );
  87.       }
  88.       return( tNode );
  89.    }
  90. }
  91.  
  92. //-----------------------------------------------------------------
  93. // Recursive node deletion routine
  94. //-----------------------------------------------------------------
  95.  
  96. DATAPTR LIBFUNC DeleteTreeNode( PTR2TREENODEPTR tree, KEYPTR key )
  97. {        
  98.    DATAPTR data;
  99.    TREENODEPTR newTree;
  100.    if ( StrCmp( key, (*tree)->inode.keyValue ) >= 0 ) {
  101.       if ( (*tree)->inode.right->nodeType == BPT_INODE ) {
  102.          data = DeleteTreeNode( (PTR2TREENODEPTR)&((*tree)->inode.right ), key );
  103.          return( data );         
  104.       } else {
  105.          if ( StrCmp( (*tree)->inode.right->lnode.keyValue, key )== 0 ) {
  106.             data = (*tree)->inode.right->lnode.data;
  107.             (*tree)->inode.right->lnode.next->lnode.prev = (*tree)->inode.right->lnode.prev;
  108.             (*tree)->inode.right->lnode.prev->lnode.next = (*tree)->inode.right->lnode.next;
  109.             FreeLNode( (*tree)->inode.right );
  110.             newTree = (*tree)->inode.left;
  111.             FreeINode( *tree );
  112.             *tree = newTree;
  113.             return( data );
  114.          } else 
  115.             return( NULL );
  116.       }
  117.    } else {
  118.       if ( (*tree)->inode.left->nodeType == BPT_INODE ) {
  119.          data = DeleteTreeNode( (PTR2TREENODEPTR)&((*tree)->inode.left ), key );
  120.          return( data );
  121.       } else {
  122.          if ( StrCmp( (*tree)->inode.left->lnode.keyValue, key ) == 0 ) {
  123.             data = (*tree)->inode.left->lnode.data;
  124.             (*tree)->inode.left->lnode.next->lnode.prev = (*tree)->inode.left->lnode.prev;
  125.             (*tree)->inode.left->lnode.prev->lnode.next = (*tree)->inode.left->lnode.next;
  126.             FreeLNode( (*tree)->inode.left );
  127.             newTree = (*tree)->inode.right;
  128.             FreeINode( *tree );
  129.             *tree = newTree;
  130.             return( data );
  131.          } else
  132.             return( NULL );
  133.       }
  134.    }
  135. }
  136.  
  137. //-----------------------------------------------------------------
  138. // Exported Function - Create a new tree
  139. //-----------------------------------------------------------------
  140.  
  141. TREEPTR LIBFUNC NewTree( ) {
  142.    TREEPTR      tree;
  143.    tree = (TREEPTR)Malloc( sizeof( TREE ) );
  144.    tree->tree = NULL;
  145.    tree->first.nodeType = BPT_LNODE;
  146.    tree->first.lnode.specialType = BPT_FIRST;
  147.    tree->first.lnode.prev = NULL;
  148.    tree->first.lnode.next = &(tree->last);
  149.    tree->last.nodeType = BPT_LNODE;
  150.    tree->last.lnode.specialType = BPT_LAST;
  151.    tree->last.lnode.next = NULL;
  152.    tree->last.lnode.prev = &(tree->first);
  153.    tree->curPointer = NULL;
  154.    return( tree );
  155. }
  156.  
  157. //-----------------------------------------------------------------
  158. // Exported Function - Insert a node in the tree
  159. //-----------------------------------------------------------------
  160.  
  161. TREENODEPTR LIBFUNC InsertInTree( TREEPTR tree, KEYPTR key, DATAPTR data ) {
  162.    TREENODEPTR tNode;
  163.    if ( tree->tree == NULL ) {
  164.       tree->tree = MakeLNode( );
  165.       tree->tree->lnode.keyValue = MakeMemBuf( StrLen( key ) + 1 );
  166.       StrCpy( tree->tree->lnode.keyValue, key );
  167.       tree->tree->lnode.data = data;
  168.       tree->tree->lnode.next = &(tree->last);
  169.       tree->tree->lnode.prev = &(tree->first);
  170.       tree->first.lnode.next = tree->tree;
  171.       tree->last.lnode.prev  = tree->tree;
  172.       tree->curPointer = tree->tree;
  173.       return( tree->tree );
  174.    } else {
  175.       tNode = InsertTreeNode( (PTR2TREENODEPTR)(&(tree->tree)), key, data );
  176.       tree->curPointer = tNode;
  177.       return( tNode );
  178.    }
  179. }
  180.  
  181. //-----------------------------------------------------------------
  182. // Exported Function - Delete a node from the tree
  183. //-----------------------------------------------------------------
  184.  
  185. DATAPTR LIBFUNC DeleteFromTree( TREEPTR tree, KEYPTR key ) {
  186.    DATAPTR data;
  187.    if ( tree->tree == NULL ) return NULL;
  188.    if ( tree->tree->nodeType == BPT_LNODE ) {
  189.       tree->first.lnode.next = &(tree->last);
  190.       tree->last.lnode.prev = &(tree->first);
  191.       data = tree->tree->lnode.data;
  192.       FreeLNode( tree->tree );     
  193.       return( data );
  194.    }
  195.    data = DeleteTreeNode( (PTR2TREENODEPTR)&(tree->tree), key ); 
  196.    return( data );
  197. }
  198.  
  199. //-----------------------------------------------------------------
  200. // Exported Functions - Sequential node access functions
  201. //-----------------------------------------------------------------
  202.  
  203. TREENODEPTR LIBFUNC FirstInTree( TREEPTR tree ) {
  204.    if ( tree->first.lnode.next == &(tree->last) ) 
  205.       return( NULL );
  206.    else
  207.       return( tree->curPointer = tree->first.lnode.next );
  208. }
  209.  
  210. TREENODEPTR LIBFUNC LastInTree( TREEPTR tree ) {
  211.    if ( tree->last.lnode.prev == &(tree->first) )
  212.       return( NULL );
  213.    else
  214.       return( tree->curPointer = tree->last.lnode.prev );
  215. }
  216.  
  217. TREENODEPTR LIBFUNC NextInTree( TREEPTR tree ) {
  218.    if ( tree->curPointer == NULL )
  219.       return( NULL );
  220.    if ( tree->curPointer->lnode.next == &(tree->last) )
  221.       return( NULL );
  222.    else
  223.       return( tree->curPointer = tree->curPointer->lnode.next );
  224. }
  225.  
  226. TREENODEPTR LIBFUNC PrevInTree( TREEPTR tree ) {
  227.    if ( tree->curPointer == NULL )
  228.       return( NULL );
  229.    if ( tree->curPointer->lnode.prev == &(tree->first) )
  230.       return( NULL );
  231.    else
  232.       return( tree->curPointer = tree->curPointer->lnode.prev );
  233. }     
  234.  
  235. //-----------------------------------------------------------------
  236. // Exported Function - Keyed node access function
  237. //-----------------------------------------------------------------
  238.  
  239. TREENODEPTR LIBFUNC FindInTree( TREEPTR tree, KEYPTR key ) {
  240.    TREENODEPTR currentNode;
  241.    if ( tree->tree == NULL )
  242.       return( NULL );
  243.    currentNode = tree->tree;
  244.    while( currentNode->nodeType != BPT_LNODE ) {
  245.       if ( StrCmp( key, currentNode->inode.keyValue ) >= 0 )
  246.          currentNode = currentNode->inode.right;
  247.       else
  248.          currentNode = currentNode->inode.left;
  249.    }
  250.    if ( StrCmp( key, currentNode->lnode.keyValue ) == 0 )
  251.       return( tree->curPointer = currentNode );
  252.    else
  253.       return( tree->curPointer = NULL );
  254. }
  255.  
  256. //-----------------------------------------------------------------
  257. // Exported Function - Data access functions
  258. //-----------------------------------------------------------------
  259.  
  260. KEYPTR LIBFUNC NodeKeyValue( TREENODEPTR tNode ) {
  261.    if ( tNode->nodeType == BPT_INODE )
  262.       return( tNode->inode.keyValue );
  263.    else
  264.       return( tNode->lnode.keyValue );
  265. }
  266.  
  267. DATAPTR LIBFUNC NodeDataValue( TREENODEPTR tNode ) {
  268.    if ( tNode->nodeType == BPT_INODE )
  269.       return( NULL );
  270.    else
  271.       return( tNode->lnode.data );
  272.